package com.gary.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author peng_rui
 * @date 2022/7/14
 */
public class BTree {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        t6.left = t2;
        t6.right = t3;
        t2.left = t1;
        t1.right = t4;
        t3.right = t5;
        List<Integer> list = new ArrayList<>();

        preOrder(list, t6);
        list.forEach(i -> {
            System.out.print(i + " ");
        });
        System.out.println();

        System.out.println(">>>>>>>>>>>>>>>>>>>>");
        List<List<Integer>> list2 = new ArrayList<>();
        levelOrder(list2, t6);
        list2.forEach(arr -> {
            for (Integer i : arr) {
                System.out.print(i + " ");
            }
            System.out.println();
        });
    }

    public static void preOrder(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        preOrder(list, root.left);
        preOrder(list, root.right);
        list.add(root.val);
    }

    /**
     * 二叉树的层序遍历
     * @param list
     * @param root
     */
    public static void levelOrder(List<List<Integer>> list, TreeNode root) {
        if (root == null) {
            return;
        }
        //使用队列 记录当前层的节点
        Queue<TreeNode> q = new ArrayDeque<>();
        //初始放入根节点
        q.add(root);
        int count = 0;
        while (!q.isEmpty()) {
            //记录层数
            count++;
            //用于获取子循环次数，即每一层有多少个节点
            int size = q.size();
            // 记录每一层节点的数据
            List<Integer> nodeList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                //从队列中弹出队列头的节点
                TreeNode node = q.poll();
                //记录节点数据
                nodeList.add(node.val);
                //将当前节点的子节点加入到队列中，即下一层的节点
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            //将当前层的数据添加到列表中
            list.add(nodeList);
        }
        System.out.println("count >> " + count);
    }

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
}


